package com.ruyuan2020.im.code;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class FourSum {
    public static List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> res = new ArrayList<>();
        int n = nums.length;
        Arrays.sort(nums);  // 首先将数组排序

        for (int i =0;i<n-3;i++){
            if (i>0&&nums[i]==nums[i-1]) continue;
            for (int j = i+1; j <n-2 ; j++) {
                if (j>i+1&&nums[j]==nums[j-1])continue;
                int left =j+1;
                int right=n-1;
                while (left<right){
                    int sum=nums[i] + nums[j] + nums[left] + nums[right];
                    if (sum == target) {
                    res.add(Arrays.asList(nums[i],nums[j],nums[left],nums[right]));
                    while (left<right&&nums[left]==nums[left+1]) left++;
                    while (left<right&&nums[right]==nums[right-1]) right--;
                    left++;
                    right--;
                }else if (sum<right){
                        left++;
                    }else {
                        right--;
                    }
                }
            }
        }

        return res;
    }

    public static void main(String[] args) {
        int[] nums = {1, 0, -1, 0, -2, 2};
        int target = 0;
        List<List<Integer>> result = fourSum(nums, target);
        for (List<Integer> list : result) {
            System.out.println(list);
        }
    }
}

